package leetcode;

import java.util.ArrayList;
import java.util.List;

import Tree.CreateByPreAndIn;
import Tree.TreeNode;

public class SumOfTreePathNumber {

	public static void main(String[] args) {
		SumOfTreePathNumber k = new SumOfTreePathNumber();
		int[] pre = {5,4,3,6,9,7,8};
		int[] in = {3,4,6,9,5,8,7};
		TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		k.sumNumbers(root);
	}
	List<Integer> path = new ArrayList<Integer>();  //存储一条路径
	List<List<Integer>> list = new ArrayList<List<Integer>>();  //存储一条路径
	
	public int sumNumbers(TreeNode root) {
		if (root == null) {
			return -1;
		}
		getPath(root);
		int sum = 0;
        for (List<Integer> onePath : list) {
        	StringBuilder number = new StringBuilder();
			for (Integer integer : onePath) {
//				System.out.println("treenode value "+ integer);
				number.append(integer);
			}
			sum += Integer.parseInt(number.toString());
//			System.out.println("number" + number.toString() + " " + sum);
		}
		return sum;
	}
	
	public void getPath(TreeNode root){
		path.add(root.val);
		// 判断是否是叶子结点
		boolean isLeaf = (root.left == null && root.right == null);
		if ( isLeaf) {
			list.add(new ArrayList<Integer>(path));
			//list.add(path); //不能这样写，因为最后将path中的结点值移除了
		}
		if ( root.left != null) {
			getPath(root.left);
		}
		if (root.right != null) {
			getPath(root.right);
		}
		//之前一直没有值，就是因为在这里将path的值给删除了，因为将path加入到list中时，List只是引用path
		//如果删除之后，那么显然就引用为空了
		
		// 在返回父节点之前，将当前的结点值删除
		path.remove(path.size() - 1);
	}
}
